Solving 10385 - Duathlon (Ternary search)
[andmenj-acm.git] / 11495 - Bubbles and buckets / 11495.cpp
blob21066bcff3dd6585ef2f03dfd8feeb49181560fa
1 using namespace std;
2 #include <algorithm>
3 #include <iostream>
4 #include <iterator>
5 #include <sstream>
6 #include <fstream>
7 #include <cassert>
8 #include <climits>
9 #include <cstdlib>
10 #include <cstring>
11 #include <string>
12 #include <cstdio>
13 #include <vector>
14 #include <cmath>
15 #include <queue>
16 #include <deque>
17 #include <stack>
18 #include <map>
19 #include <set>
21 int numbers[100001];
22 int a[50005], b[50005];
23 int n;
27 Sorts the elements from numbers [start ... end) in decreasing order
28 and returns the number of inversions in that piece of array.
30 long long merge_sort(int start, int end){
31 long long cnt = 0;
32 if (start + 1 == end){ //Single element
33 return cnt;
36 int m = (start + end)/2;
37 cnt += merge_sort(start, m) + merge_sort(m, end);
39 int _a = m - start, _b = end - m;
40 for (int i=start; i<start+_a; ++i){
41 a[i-start] = numbers[i];
44 for (int i=m; i<m+_b; ++i){
45 b[i-m] = numbers[i];
48 for (int i=0, j=0; i<_a && j<_b; ){
49 if (a[i] > b[j]){
50 cnt += (long long)(_b - j);
51 ++i;
52 }else{
53 ++j;
57 a[_a] = b[_b] = -1;
59 for (int k=start, i=0, j=0; k<end; ++k){
60 if (a[i] > b[j]){
61 numbers[k] = a[i++];
62 }else{
63 numbers[k] = b[j++];
67 return cnt;
71 int main(){
72 while (scanf("%d", &n)==1 && n){
73 for (int i=0; i<n; ++i){
74 scanf("%d", &numbers[i]);
77 long long cnt = merge_sort(0, n);
78 //printf("%lld\n", cnt);
79 puts((cnt % 2 ? "Marcelo" : "Carlos"));
81 return 0;